class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target)
    {
        int m = matrix.size(), n = matrix[0].size();

        int u = 0, d = m - 1, l = 0, r = n - 1;

        while (l <= r && u <= d)
        {
            if (matrix[d][l] < target) l++;
            else if (matrix[d][l] > target) d--;
            else return true;

            if (matrix[u][r] < target) u++;
            else if (matrix[u][r] > target) r--;
            else return true;
        }
        return false;
    }
};